package Test;

import java.util.Stack;

public class 最长有效括号 {
    public static int longestValidParentheses(String s) {
        int[] dp=new int[s.length()+1];
        Stack<Integer> s1=new Stack();
        for (int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                s1.push(i);
                dp[i+1]=0;
            }else {
                if(!s1.isEmpty()){
                    int left=s1.pop();
                    dp[i+1]=i-left+1+dp[left];
                }else {
                    dp[i+1]=0;
                }
            }
        }
        int res=0;
        for (int i:dp){
            res=Math.max(i,res);
        }
        return res;
    }
}
